package cn.zzf.algs.note.base.collection.v2;

import cn.zzf.algs.note.base.struct.Node;

import java.util.HashMap;
import java.util.Iterator;

/**
 * 双向链表实现的容器
 * @author GaoFeng2017
 * @date 2020/6/12 14:56
 */
public class LinkedList<T> implements List<T> {

    /** 首节点 */
    private Node<T> first;

    /** 尾节点 */
    private Node<T> last;

    /** 当前容器元素数量 */
    private int size;

    /** 向栈顶推送一个元素 */
    @Override
    public void push(T element) {

        if (this.first == null) {
            this.first = new Node<>(element, null, null);
        } else {
            // 1,null -> 2,1,null  null <- 2 <- 1   2 <- 1 <- null
            // 双向关联，对于新节点来说，旧结点的prev要指向新节点，新节点的next指向旧结点，同时first指向新结点。
            Node<T> node = new Node<>(element);
            node.setNext(this.first);
            this.first.setPrev(node);
            this.first = node;
        }

        this.size++;

    }

    /** 从栈顶弹出一个元素 */
    @Override
    public T pop() {
        return this.dequeue();
    }

    /** 删除尾节点元素 */
    @Override
    public T removeLast() {
        if (this.last == null) {
            return null;
        }

        T element = this.last.getValue();
        this.last = this.last.getPrev();

        if (this.last == null) {
            this.first = null;
        }

        this.size--;
        return element;
    }

    @Override
    public int size(){
        return this.size;
    }

    /** 将元素添加到队尾 */
    @Override
    public void enqueue(T element) {

        if (this.last == null) {
            this.last = new Node<>(element, null, null);
            this.first = this.last;
        } else {
            // 1,null -> 1,2,null , null <- 1 -> 2 , 1 <- 2 -> null
            // 双向关联，对于新节点来说，旧结点的next需要指向新节点，同时新节点的prev需要指向旧结点
            Node<T> node = new Node<>(element);
            node.setPrev(this.last);
            this.last.setNext(node);
            this.last = node;
        }


        this.size++;

    }

    /** 从队首弹出一个元素 */
    @Override
    public T dequeue() {

        if (this.first == null) {
            return null;
        }

        T element = this.first.getValue();
        this.first = this.first.getNext();

        if (this.first == null) {
            this.last = null;
        }

        this.size--;
        return element;
    }

    /** 删除指定位置的结点 */
    @Override
    public T removeAt(int index) {

        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException();
        }

        if (first == null) {
            return null;
        }

        T element = null;

        // 只有一个节点
        if (this.size == 1) {
            element = this.first.getValue();
            this.first = null;
            this.last = null;
            return element;
        }

        int currentIndex = 0;
        for (Node<T> currentNode = this.first; currentNode != null; currentNode = currentNode.getNext()) {

            if (currentIndex != index) {
                currentIndex++;
                continue;
            }

            element = currentNode.getValue();

            if (currentNode.getPrev() != null) {
                currentNode.getPrev().setNext(currentNode.getNext());
            }

            if (currentNode.getNext() != null) {
                currentNode.getNext().setPrev(currentNode.getPrev());
            }

            break;
        }

        this.size--;
        return element;
    }

    /** 向指定位置插入节点 */
    @Override
    public void insertAt(T element, int index) {

        if (index < 0 || index > this.size) {
            throw new IndexOutOfBoundsException();
        }

        if (index == 0) {
            this.push(element);
            return;
        }

        if (index == this.size) {
            this.enqueue(element);
            return;
        }

        int currentIndex = 0;

        for (Node<T> currentNode = this.first; currentNode != null; currentNode = currentNode.getNext()) {

            if (currentIndex != index - 1) {
                currentIndex++;
                continue;
            }

            Node<T> node = new Node<>(element);


            node.setNext(currentNode.getNext());
            node.setPrev(currentNode);

            currentNode.setNext(node);
            currentNode.getNext().setPrev(node);

            break;

        }

        this.size++;

    }



    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            /** 当前节点 */
            private Node<T> currentNode = first;

            @Override
            public boolean hasNext() {
                return currentNode != null;
            }

            @Override
            public T next() {
                T element = currentNode.getValue();
                this.currentNode = currentNode.getNext();
                return element;
            }
        };
    }

    @Override
    public String toString() {
        HashMap<Node<T>, String> nodeMap = new HashMap<>(16);

        Node<T> currentNode = this.first;
        StringBuilder result = new StringBuilder();
        result.append("{");

        while (currentNode != null) {

            result.append("Node{value=")
                    .append(currentNode.getValue())
                    .append(", prev=")
                    .append(nodeMap.get(currentNode.getNext()))
                    .append(", next=")
                    .append(nodeMap.get(currentNode.getNext()))
                    .append("}, ");


            nodeMap.put(currentNode, result.toString());
            currentNode = currentNode.getNext();


        }

        return result.append("}").toString();

    }


}
